package com.gozap.sort.spec;

public class MergeSort {

	/**
	 * 
	 * @param arr
	 * @param begin数组下标
	 * @param end数组下标
	 */
	public void merge(int[] arr, int begin, int end) {
		if (end > begin) {
			int mid = (begin + end) / 2;

			merge(arr, begin, mid);
			merge(arr, mid + 1, end);

			int len = end - begin + 1;
			int[] copy = new int[len];
			int i = 0;
			int b = begin;
			int a = mid + 1;

			while (b <= mid && a <= end) {
				if (arr[b] < arr[a]) {
					copy[i] = arr[b];
					b++;
				} else {
					copy[i] = arr[a];
					a++;
				}
				i++;
			}
			if (b > mid) {
				for (int j = i; j < len; j++) {
					copy[j] = arr[a];
					a++;
				}
			} else if (a > mid) {
				for (int j = i; j < len; j++) {
					copy[j] = arr[b];
					b++;
				}
			}

		}
	}

	// static int arr[] = { 4, 5, 3, 9, 8, 7, 98, 72, 10, 12, 8, 6, 20, 15, 60,
	// 45, 2, 43, 11, 50 };

	public static void print(int[] arr) {
		int len = arr.length;
		for (int i = 0; i < len; i++) {
			System.out.print(arr[i] + " ");
		}
	}

	public static void main(String[] args) {
		int arr[] = { 4, 3 };

		new MergeSort().merge(arr, 0, arr.length - 1);
		print(arr);
		System.out.println("======");
	}
}
